#include "../include/backtrack.h"

// 回溯法辅助函数
static void backtrack_helper(Item* items, int n, int capacity,
                           int current_index, int current_weight,
                           double current_value, int* current_selection,
                           int* best_selection, double* best_value,
                           int* best_count) {
    // 如果已经处理完所有物品或背包已满
    if (current_index == n || current_weight >= capacity) {
        if (current_value > *best_value) {
            *best_value = current_value;
            *best_count = current_index;
            memcpy(best_selection, current_selection, n * sizeof(int));
        }
        return;
    }

    // 不选当前物品
    backtrack_helper(items, n, capacity, current_index + 1,
                    current_weight, current_value,
                    current_selection, best_selection,
                    best_value, best_count);

    // 选当前物品（如果不超过容量）
    if (current_weight + items[current_index].weight <= capacity) {
        current_selection[current_index] = 1;
        backtrack_helper(items, n, capacity, current_index + 1,
                        current_weight + items[current_index].weight,
                        current_value + items[current_index].value,
                        current_selection, best_selection,
                        best_value, best_count);
        current_selection[current_index] = 0;
    }
}

Result backtrack_knapsack(Item* items, int n, int capacity) {
    Result result = {0};
    LARGE_INTEGER start, end, freq;
    QueryPerformanceFrequency(&freq);
    QueryPerformanceCounter(&start);

    // 分配内存
    result.selected_items = (int*)malloc(n * sizeof(int));
    int* current_selection = (int*)malloc(n * sizeof(int));
    int* best_selection = (int*)malloc(n * sizeof(int));
    
    if (!result.selected_items || !current_selection || !best_selection) {
        printf("Memory allocation failed\n");
        free(result.selected_items);
        free(current_selection);
        free(best_selection);
        return result;
    }

    // 初始化
    memset(current_selection, 0, n * sizeof(int));
    memset(best_selection, 0, n * sizeof(int));
    double best_value = 0;
    int best_count = 0;

    // 执行回溯
    backtrack_helper(items, n, capacity, 0, 0, 0,
                    current_selection, best_selection,
                    &best_value, &best_count);

    // 收集结果
    result.total_value = best_value;
    result.selected_count = 0;
    for (int i = 0; i < n; i++) {
        if (best_selection[i]) {
            result.selected_items[result.selected_count++] = items[i].id;
        }
    }

    // 释放内存
    free(current_selection);
    free(best_selection);

    // 计算执行时间
    QueryPerformanceCounter(&end);
    result.time_taken = (double)(end.QuadPart - start.QuadPart) * 1000.0 / freq.QuadPart;

    // 计算内存使用
    result.memory_used = sizeof(Result) + n * sizeof(int) * 3;  // 包括临时数组

    return result;
} 